/*
 * File:   10009.cpp
 * Author: xerxes
 *
 * Created on September 17, 2011, 12:55 PM
 *
 * I have not failed, I have just found 10000 ways that won't work.
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define VI vector< int >
#define CI( x ) scanf("%d",&x)
#define CL( x ) scanf("%lld",&x)
#define CD( x ) scanf("%lf",&x )
#define fo(i,st,ed) for(int i = st ; i < ed ; ++i )
#define foE(i,st,ed) for(int i = st ; i <= ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

inline void wait(double seconds) {
    double endtime = clock()+(seconds * CLOCKS_PER_SEC);
    while (clock() < endtime) {
        ;
    }
}

int id[30];
char revid[30];

int nRoad, nQuery;
vector< VI > path;

inline void Read() {
    CI(nRoad);
    CI(nQuery);
    SET(id, -1);

    vector< pair<int, int> > vi;
    int x = 0;
    string s1, s2;

    fo(i, 0, nRoad) {
        cin >> s1 >> s2;
        char c1 = s1[0];
        char c2 = s2[0];

        if (id[ c1 - 'A'] == -1) {
            id[ c1 - 'A' ] = x;
            revid[ x ] = c1;
            ++x;
        }
        if (id[ c2 - 'A'] == -1) {
            id[ c2 - 'A' ] = x;
            revid[ x ] = c2;
            ++x;
        }
        vi.pb(mk(id[ c1 - 'A' ], id[ c2 - 'A' ]));
    }

    path.assign(x + 5, VI());
    for (int i = 0, j = SZ(vi); i < j; ++i) {
        int id1 = vi[i].f;
        int id2 = vi[i].s;
        path[ id1 ].pb(id2);
        path[ id2 ].pb(id1);
    }
}

inline void Print(VI &vt) {
    string ss = "";
    for (int i = 0, j = SZ(vt); i < j; ++i) {
        ss += revid[ vt[i] ];
    }
    cout << ss << "\n";
}
int vis[ 27 ];

inline void bfs(int sx, int dx) {
    SET(vis, 0);
    queue< pair<int, VI > > q;

    q.push(mk(sx, VI(1, sx)));
    vis[ sx ] = 1;

    while (q.empty() == false) {
        int father = q.front().f;
        VI agerAmi = q.front().s;
        q.pop();
        //cout<<"Now father : "<<father<<"\n";wait(1);
        if (father == dx) {
            Print(agerAmi);
            return;
        }
        for (int i = 0, j = SZ(path[father]); i < j; ++i) {
            int child = path[father][i];
            if (vis[child])continue;

            VI akhonAmi = agerAmi;
            akhonAmi.pb(child);
            q.push(mk(child, akhonAmi));
            vis[ child ] = 1;

        }

    }
    //kill never come
}

inline void Proc() {
    string s1, s2;

    fo(i, 0, nQuery) {
        cin >> s1 >> s2;
        char c1 = s1[0];
        char c2 = s2[0];
        bfs(id[ c1 - 'A' ], id[ c2 - 'A' ]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "rt", stdin);
#endif
    int cases = 1;
    string ss = "";
    for (CI(cases); cases; --cases) {
        Read();
        cout << ss;
        Proc();
        ss = "\n";
    }

    return 0;
}


